1 const int MAXN
= 105, oo
= INT_MAX
/ 2 - 1;
10 pair
<int, int> min_cost_max_flow(int N
, int source
, int sink
)
11 { int flowSize
= 0; int flowCost
= 0; int infinity
= 1;
12 while (2*infinity
> infinity
) infinity
*= 2;
13 // speed optimization #1: adjacency graph
14 // speed optimization #2: cache the degrees
15 vector
<int> deg(N
,0); vector
<vector
<int> > G(N
); for (int
16 i
=0; i
<N
; i
++) for (int j
=0; j
<i
; j
++) if (cap
[i
][j
]>0 ||
17 cap
[j
][i
]>0) { deg
[i
]++; deg
[j
]++; G
[i
].push_back(j
);
18 G
[j
].push_back(i
); } vector
<int> potential(N
,0); while (1) {
19 // use dijkstra to find an augmenting path
20 vector
<int> from(N
,-1); vector
<int> dist(N
,infinity
);
21 priority_queue
< pair
<int,int>, vector
<pair
<int,int> >,
22 greater
<pair
<int,int> > > Q
; Q
.push(make_pair(0,source
));
23 from
[source
]=-2; dist
[source
] = 0; while (!Q
.empty()) {
24 int howFar
= Q
.top().first
; int where
= Q
.top().second
;
25 Q
.pop(); if (dist
[where
] < howFar
) continue; for (int i
=0;
26 i
<deg
[where
]; i
++) { int dest
= G
[where
][i
];
27 // now there are two possibilities: add flow in
28 // the right direction, or remove in the other one
29 if (flow
[dest
][where
] > 0) if (dist
[dest
] >
30 dist
[where
] + potential
[where
] - potential
[dest
] -
31 cost
[dest
][where
]) { dist
[dest
] = dist
[where
] +
32 potential
[where
] - potential
[dest
] -
33 cost
[dest
][where
]; from
[dest
] = where
;
34 Q
.push(make_pair(dist
[dest
],dest
)); } if
35 (flow
[where
][dest
] < cap
[where
][dest
]) if
36 (dist
[dest
] > dist
[where
] + potential
[where
] -
37 potential
[dest
] + cost
[where
][dest
]) { dist
[dest
] =
38 dist
[where
] + potential
[where
] - potential
[dest
] +
39 cost
[where
][dest
]; from
[dest
] = where
;
40 Q
.push(make_pair(dist
[dest
],dest
)); }
41 // no breaking here, we need the whole graph
43 // update vertex potentials
44 for (int i
=0; i
<N
; i
++) potential
[i
] += dist
[i
];
45 // if there is no path, we are done
46 if (from
[sink
] == -1) return make_pair(flowSize
,flowCost
);
47 // construct an augmenting path
48 int canPush
= infinity
; int where
= sink
; while (1) { int
49 prev
=from
[where
]; if (prev
==-2) break; if
50 (flow
[where
][prev
]) canPush
= min( canPush
,
51 flow
[where
][prev
] ); else canPush
= min( canPush
,
52 cap
[prev
][where
] - flow
[prev
][where
] ); where
=prev
; }
53 // update along the path
54 where
= sink
; while (1) { int prev
=from
[where
]; if
55 (prev
==-2) break; if (flow
[where
][prev
]) {
56 flow
[where
][prev
] -= canPush
; flowCost
-= canPush
*
57 cost
[where
][prev
]; } else { flow
[prev
][where
] += canPush
;
58 flowCost
+= canPush
* cost
[prev
][where
]; } where
=prev
; }
59 flowSize
+= canPush
; } return make_pair(0, oo
); }
